package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

/**
 * 递归判断作用子树是否是搜索二叉树，时间复杂度为O(n),空间复杂度为 O(n)
 */
public class _14_判断二叉树是否为搜索二叉树 {

    private static class TreeInfo{

        boolean isSearchBinaryTree;
        int max;
        int min;
    }

    public static boolean isSearchBinaryTree(TreeNode root) {

        if (root == null) {

            return false;
        }

        return postTraversalTree(root).isSearchBinaryTree;
    }

    public static TreeInfo postTraversalTree(TreeNode node) {
        if (node == null) {

            return null;
        }

        TreeInfo leftInfo = postTraversalTree(node.left);
        TreeInfo rightInfo= postTraversalTree(node.right);

        if (leftInfo == null && rightInfo == null) {

            TreeInfo treeInfo = new TreeInfo();
            treeInfo.isSearchBinaryTree = true;
            treeInfo.max = node.val;
            treeInfo.min = node.val;
            return treeInfo;
        }

        if (leftInfo == null && rightInfo != null) {

            if (!rightInfo.isSearchBinaryTree || node.val > rightInfo.min) {

                rightInfo.isSearchBinaryTree = false;
                return rightInfo;
            }

            rightInfo.min = node.val;
            return rightInfo;
        }

        if (leftInfo != null && rightInfo == null) {

            if (!leftInfo.isSearchBinaryTree || node.val < leftInfo.max) {

                leftInfo.isSearchBinaryTree = false;
                return leftInfo;
            }

            leftInfo.max = node.val;
            return leftInfo;
        }

        if (!leftInfo.isSearchBinaryTree || !rightInfo.isSearchBinaryTree ||
                node.val < leftInfo.max || node.val > rightInfo.min) {

            leftInfo.isSearchBinaryTree = false;
            return leftInfo;
        }

        leftInfo.max = rightInfo.max;
        return leftInfo;
    }

    public static void main(String[] args) {

        /**
         *                  6
         *
         *               3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(7);
        t1.right.right = new TreeNode(10);

        System.out.println(isSearchBinaryTree(t1));

    }
}
